#include "Graph.h"

Graph::Graph():Numiterator(0),maxflow(0),ScaleValue(0)
{
	ReadGraph();//ctor
}

Graph::~Graph()
{
	for( int i=0;i<Nodenum;i++)
	{
		delete[] GraphCapFlow[i];
		delete[] ReGraphCapFlow[i];
	}

	delete[] GraphCapFlow;
	delete[] ReGraphCapFlow;
	for(int j =0;j<Nodenum;j++)
	{
		node_t* pnode;
		while(pGraphArray[j].next != NULL)
		{
			pnode = pGraphArray[j].next;
			pGraphArray[j].next = pnode->next;
			delete pnode;
		}
	}
	delete[] pGraphArray;
	for(int j =0;j<Nodenum;j++)
	{
		node_t* pnode;
		while(pReGraphArray[j].next != NULL)
		{
			pnode = pReGraphArray[j].next;
			pReGraphArray[j].next = pnode->next;
			delete pnode;
		}
	}
	delete[] pReGraphArray;

	for(int j =0;j<Nodenum;j++)
	{
		node_t* pnode;
		while(pScaleGraph[j].next != NULL)
		{
			pnode = pScaleGraph[j].next;
			pScaleGraph[j].next = pnode->next;
			delete pnode;
		}
	}
	delete[] pScaleGraph;
}

void Graph::CalscaleValue()
{
	if (pGraphArray[0].next == NULL)
		return;
	node_t* pnode = pGraphArray[0].next;
	int nMax = 0;
	while (pnode != NULL)
	{
		nMax = GraphCapFlow[0][pnode->i].cap > nMax ? GraphCapFlow[0][pnode->i].cap: nMax;
		pnode = pnode->next;
	}
	int i = 2;
	while (i<nMax)
	{
		i = i*2;
	}
	ScaleValue = i/2;
	outfile<<"ScaleValue: "<<ScaleValue<<endl;

}

void Graph::ReadGraph()
{
	FILE * is = fopen( "input.txt", "r" );
	if( is == NULL )
	{
		return;
	}
	int inum = 0;
	char line[MAXLINE];
	int checking,init, dest, cap;
	while(!feof(is)) //when the file ends, feof return non-zero
	{
		if(fgets(line,  MAXLINE, is) == NULL) break;
		char* str = strtok(line," ");
		switch (inum){
		case 0:
			Nodenum = atoi(str);
			str = strtok(NULL," ");
			Edgenum = atoi(str);
			GraphCapFlow = new CapAndFlow*[Nodenum];
			ReGraphCapFlow = new int*[Nodenum];
			pGraphArray = new node_t[Nodenum];
			pReGraphArray = new node_t[Nodenum]; //Construct the scale graph
			pScaleGraph = new node_t[Nodenum];
			for(int i = 0; i<Nodenum;i++)
			{
				GraphCapFlow[i]=new CapAndFlow[Nodenum];
				ReGraphCapFlow[i]=new int[Nodenum];
			}
			for(int i = 0; i<Nodenum;i++)
				for(int j = 0; j<Nodenum;j++)
				{
					GraphCapFlow[i][j].cap = -1;
					GraphCapFlow[i][j].flow = 0;
					ReGraphCapFlow[i][j] = -1;
				}
				break;

		case 1:
			Source = atoi(str)-1;
			str = strtok(NULL," ");
			Sink = atoi(str)-1;
			str = strtok(NULL," ");
			checking = atoi(str);
			if(checking != Sink-Source)
				return;
			break;
		default:
			init = atoi(str);
			str = strtok(NULL," ");
			dest = atoi(str);
			str = strtok(NULL," ");
			cap = atoi(str);
			init--;
			dest--;
			//construct the Graph: adjacency List
			node_t* pIndex = pGraphArray+ init;
			pIndex->i = init;
			node_t* pNode = new node_t;
			pNode->i = dest;
			pNode->next = pIndex->next;
			pIndex->next = pNode;
			//2.assign the cap and flow value
			GraphCapFlow[init][dest].cap = cap;
			GraphCapFlow[init][dest].flow = 0;

			//construct the Residual Graph
			node_t* pReIndex = pReGraphArray + init;
			pReIndex->i= init;
			node_t* pReNode = new node_t;
			pReNode->i = dest;
			pReNode->next = pReIndex->next;
			pReIndex->next = pReNode;
			ReGraphCapFlow[init][dest] = cap;

			//cout<<"init:"<<init<<"   "<<"dest:"<<dest<<"    "<<"cap:"<<cap<<endl;
			break;

		}
		inum++;
	}
	CalscaleValue();
	outfile.open("output.txt");

#ifdef debug
	for(int i = 0; i< Nodenum; i++){
		for(int j = 0; j<Nodenum; j++)
		{
			cout<<"("<<GraphCapFlow[i][j].cap<<","<<GraphCapFlow[i][j].flow<<")"<<": "<<ReGraphCapFlow[i][j]<<"  ";
		}
		cout<<endl;
	}
#endif // debug
}

bool Graph::IsAugPath()
{
	//using Breath First Search Algorithm
	int* NodeIndex = new int[Nodenum];
	int* PaNode = new int[Nodenum];
	for(int j = 0;j<Nodenum; j++)
	{
		NodeIndex[j] = 0;
		PaNode[j] = -1; //save the parent Node
	}
	queue<int> nodequeue;
	node_t anode; //= pReGraphArray[0];
	nodequeue.push(0);
	NodeIndex[0] = 1;
	int n = Sink;
	//AugPath.push_back(n);
	while(!nodequeue.empty())
	{
		int nIndex = nodequeue.front();
		nodequeue.pop();
		anode = pReGraphArray[nIndex];
		while(anode.next != NULL )
		{
			if(NodeIndex[anode.next->i] == 1) //The node has added to the path
			{
				anode = *(anode.next);
				continue;
			}
			if(ReGraphCapFlow[pReGraphArray[nIndex].i][anode.next->i] < ScaleValue) //There is no capacity for the edge
			{
				anode = *(anode.next);
				continue;
			}
			nodequeue.push(anode.next->i);
			NodeIndex[anode.next->i] = 1;
			PaNode[anode.next->i] = pReGraphArray[nIndex].i;
			if(anode.next->i == n)
			{
				AugPath.clear();
				while(n != Source)
				{
					AugPath.push_front(n);
					n = PaNode[n];
				}
				AugPath.push_front(Source);
				Numiterator++;
				delete[] NodeIndex;
				delete[] PaNode;
				outfile<<"The augment path at iteration "<<Numiterator<<" is:"<<endl;
				for(list<int>::iterator j = AugPath.begin();j != AugPath.end();++j)
					outfile<<*j+1<<"    ";
				outfile<<endl;

#ifdef debug
				for(list<int>::iterator j = AugPath.begin();j != AugPath.end();++j)
				{
					int n = *j;
					cout<<n+1<<endl;
				}

#endif // debug
				return true;
			}
			anode = *(anode.next);
		}

	}
	delete[] NodeIndex;
	delete[] PaNode;
	return 0;
	//    int n;
	//    AugPath.push_back(anode.next->i);
	//    n = PaNode[anode.next->i];
	//    AugPath.push_back(PaNode[n])
	//    while()
	//    {
	//        AugPath.push_back(PaNode[anode.next->i]);
	//    }



}


void Graph::UpdateFlow()
{
	//caculate the bottleneck
	int n = AugPath.size();
	//    int* nArray = new int[n];
	if(n>2)
	{
		list<int>::iterator j = AugPath.begin();
		int pre, next;
		pre = AugPath.front();
		next = *(++j);
		bottleneck = ReGraphCapFlow[pre][next];
		for(;j != AugPath.end();j++)
		{
			//pre = *(j++);
			next = *j;
			bottleneck = bottleneck < ReGraphCapFlow[pre][next] ? bottleneck : ReGraphCapFlow[pre][next];
			pre = next;
		}
		maxflow += bottleneck;
		outfile<<"bottlenect: "<<bottleneck<<"	"<<"Scalevalue: "<<ScaleValue<<endl<<endl;
		//        pre = *(j++);
		//        next = *j;
		//        bottleneck = bottleneck < ReGraphCapFlow[pre][next] ? bottleneck : ReGraphCapFlow[pre][next];
		//adjuct the flow of Graph
		j = AugPath.begin();
		pre = AugPath.front();
		++j;
		//        if(GraphCapFlow[pre][next].cap == -1)
		//            GraphCapFlow[pre][next].flow = GraphCapFlow[pre][next].flow - bottleneck;
		//        else
		//            GraphCapFlow[pre][next].flow = GraphCapFlow[pre][next].flow + bottleneck;
		for(;j != AugPath.end();j++)
		{
			next = *j;
			if(GraphCapFlow[pre][next].cap == -1)
				GraphCapFlow[pre][next].flow -= bottleneck;
			else
				GraphCapFlow[pre][next].flow += bottleneck;
			pre = next;
		}

#ifdef debug
		cout<<endl<<"updateFlow:"<<endl;
		cout<<"Numiterator: "<<Numiterator<<endl;
		cout<<"bottleneck: "<< bottleneck<<endl;
		for(int i = 0; i< Nodenum; i++){
			for(int j = 0; j<Nodenum; j++)
			{
				cout<<"("<<GraphCapFlow[i][j].cap<<","<<GraphCapFlow[i][j].flow<<")"<<": "<<ReGraphCapFlow[i][j]<<"  ";
			}
			cout<<endl;
		}

#endif // debug
		return;
	}
	else if(n == 2)
	{
		GraphCapFlow[Source][Sink].flow =+ ReGraphCapFlow[Source][Sink];
		return;
	}
	else
		return;


}

void Graph::ChangeReflow(int& pre, int& next)
{
	if(GraphCapFlow[pre][next].flow<=GraphCapFlow[pre][next].cap)
	{
		ReGraphCapFlow[pre][next] = GraphCapFlow[pre][next].cap-GraphCapFlow[pre][next].flow;
	}
	if(GraphCapFlow[pre][next].flow > 0)
	{
		if(ReGraphCapFlow[next][pre] == -1) //There is no such path in Graph, so we such add this node to the Residual Graph.
		{
			node_t* pnode = new node_t;
			pnode->i = pre;
			pnode->next = pReGraphArray[next].next;
			pReGraphArray[next].next = pnode;
		}
		ReGraphCapFlow[next][pre] = GraphCapFlow[pre][next].flow;

	}
}

void Graph::ConReGraph()
{
	list<int>::iterator j = AugPath.begin();
	int pre, next;
	pre = AugPath.front();
	for(++j;j != AugPath.end();j++)
	{
		next = *j;
		ChangeReflow(pre, next);
		pre = next;
	}
#ifdef debug
	cout<<endl<<"Residual Graph:"<<endl;
	for(int i = 0; i< Nodenum; i++){
		for(int j = 0; j<Nodenum; j++)
		{
			cout<<"("<<GraphCapFlow[i][j].cap<<","<<GraphCapFlow[i][j].flow<<")"<<": "<<ReGraphCapFlow[i][j]<<"  ";
		}
		cout<<endl;
	}

#endif // debug
}

void Graph::mincut()
{
	int* NodeIndex = new int[Nodenum];
	for(int j = 0;j<Nodenum; j++)
		NodeIndex[j] = 0;
	queue<int> nodequeue;
	node_t anode; //= pReGraphArray[0];
	nodequeue.push(0);
	NodeIndex[0] = 1;
	while(!nodequeue.empty())
	{
		int nIndex = nodequeue.front();
		nodequeue.pop();
		anode = pReGraphArray[nIndex];
		while(anode.next != NULL )
		{
			if(NodeIndex[anode.next->i] == 1)
			{
				anode = *(anode.next);
				continue;
			}
			if(ReGraphCapFlow[pReGraphArray[nIndex].i][anode.next->i] == 0)
			{
				anode = *(anode.next);
				continue;
			}
			nodequeue.push(anode.next->i);
			NodeIndex[anode.next->i] = 1;
			anode = *(anode.next);
		}
	}
	outfile<<endl<<"Min-cut capacity = "<< maxflow<<endl;
	outfile<<"The min-cut is"<<endl;
	for(int k=0;k<Nodenum;k++)
	{
		if(NodeIndex[k] == 1)
			outfile<<k+1<<" ";
	}
	outfile<<endl;
	for(int k=0;k<Nodenum;k++)
	{
		if(NodeIndex[k] != 1)
			outfile<<k+1<<" ";
	}
	delete[] NodeIndex;
}

//void Graph::UpdateScaleGraph()
//{
//	for(int k = 0; k<Nodenum;Nodenum++)
//	{
//		pScaleGraph[0] = pReGraphArray[0];
//		node_t* pnode = pReGraphArray[0].next;
//		while (pnode != NULL && )
//		{
//		}
//	}
//}

void Graph::FordFulkersonAlg()
{
	while (ScaleValue != 1)
	{
		while(IsAugPath())//exist Augment Path, and using list save the path
		{
			UpdateFlow();
			ConReGraph();
		}
		ScaleValue = ScaleValue/2;
	}

	while(IsAugPath())//exist Augment Path, and using list save the path
	{
		UpdateFlow();
		ConReGraph();
		outfile<<"bottlenect: "<<bottleneck<<"	"<<"Scalevalue: "<<ScaleValue<<endl<<endl;
	}
	outfile<<endl<<"Flow value = "<<maxflow<<endl;
	outfile<<"The max-flow is: "<<endl;
	node_t* pnode;
	for(int j = 0; j<Nodenum;j++)
	{
		if(pGraphArray[j].next == NULL)
			continue;
		pnode = pGraphArray[j].next;
		while(pnode != NULL)
		{
			outfile<<pGraphArray[j].i+1<<" "<<pnode->i+1<<" ";
			outfile<<GraphCapFlow[pGraphArray[j].i][pnode->i].flow<<endl;
			pnode = pnode->next;
		}
	}
	mincut();
	outfile.close();
}
